package com.berchen.查找;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 二分查找算法
 */
public class BinarySearch {
    public static void main(String[] args){

        int arr[]={1,2,4,6,6,6,6,6,7,8,10};

        // JDK 自带二分查找
        System.out.println(Arrays.binarySearch(arr, 7));


        int i = binarySearch(arr, 7);
        System.out.println(i);

        List<Integer> integers = binarySearch1(arr, 6);
        System.out.println(integers);

        int i1 = binaryDiGuiSearch(arr, 0, 8, arr.length - 1);
        System.out.println(i1);
    } 

    /**
     * 递归查找
     * @param arr
     * @param start
     * @param value
     * @param end
     * @return
     */
    public static int binaryDiGuiSearch(int[] arr ,int start ,int value ,int end){

        if(start>end){
            return -1;
        }
        int mid=(start+end)/2;
        if(arr[mid]<value){
            return binaryDiGuiSearch(arr,mid+1,value,end);
        }
        else if(arr[mid]>value){
           return binaryDiGuiSearch(arr,start,value,end-1);
        }
        else
            return mid;
    }

    /**
     * 非递归查找
     * @param arr
     * @param value
     * @return
     */
    public static int binarySearch(int [] arr ,int value){

        int left=0;
        int right=arr.length-1;
        int mid =0;
        while (true){
            if(left>right){
                return -1;
            }
            mid=(left+right)/2;
            if(arr[mid]<value){
                left=mid+1;
            }
            if(arr[mid]>value){
                right=mid-1;
            }
            if(arr[mid]==value){
                return mid;
            }
        }
    }
    public static List<Integer> binarySearch1(int [] arr , int value){

        List<Integer> list=new ArrayList<>();
        int left=0;
        int right=arr.length-1;
        int mid =0;
        while (true){
            if(left>right){
                return new ArrayList<>();
            }
            mid=(left+right)/2;
            if(arr[mid]<value){
                left=mid+1;
            }
            if(arr[mid]>value){
                right=mid-1;
            }
            if(arr[mid]==value){
                int tempIndex=mid-1;
                while (tempIndex>0&&arr[tempIndex]==value){
                    list.add(tempIndex--);
                }
                list.add(mid);
                tempIndex=mid+1;
                while (tempIndex<arr.length&&arr[tempIndex]==value){
                    list.add(tempIndex++);
                }
                return list;
            }
        }
    }
}
